package com.dyz.leetcode._09_heapAndPriorityQueue;

public class _4_findMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m>n){
            return findMedianSortedArrays(nums2, nums1);
        }
        int start = 0;
        int end = m;
        double result =0.0;
        while (start<=end){
            int mid = start +(end-start)/2;//第一个左边贡献多少的位置
            int other = (m+n+1) /2 -mid;    // 第二个数组左边贡献多少的位置

            int nums1LeftMax = mid==0?Integer.MIN_VALUE:nums1[mid-1];
            int nums1RightMin = mid==m?Integer.MAX_VALUE:nums1[mid];
            int nums2LeftMax = other==0?Integer.MIN_VALUE:nums2[other-1];
            int nums2RightMin = other==n?Integer.MAX_VALUE:nums2[other];

            if(nums1LeftMax<=nums2RightMin && nums1RightMin>=nums2LeftMax){
                if((n+m)%2==0){
                    int max = Math.max(nums1LeftMax, nums2LeftMax);
                    int min = Math.min(nums1RightMin, nums2RightMin);
                    result=  (max+min)/2.0;
                }else{
                    result= Math.max(nums1LeftMax, nums2LeftMax)*1.0;
                }
                break;
            }else if(nums1RightMin<nums2LeftMax){
                start = mid+1;
            }else {
                end = mid-1;
            }
        }
        return result;
    }
}
